#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <vector>
#include <string>

using namespace std;

class Solution1 {
    int dx[4] = { 0, 0, 1, -1 };
    int dy[4] = { 1, -1, 0, 0 };
    int m, n;
    bool Pvis[210][210] = { 0 };
    bool Avis[210][210] = { 0 };
public:
    vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
        m = heights.size(), n = heights[0].size();
        for (int i = 0; i < m; i++) {
            if (!Pvis[i][0]) {
                Pvis[i][0] = true;
                dfs(heights, i, 0, 0);
            }
            if (!Avis[i][n - 1]) {
                Avis[i][n - 1] = true;
                dfs(heights, i, n - 1, 1);
            }
        }
        for (int j = 0; j < n; j++) {
            if (!Pvis[0][j]) {
                Pvis[0][j] = true;
                dfs(heights, 0, j, 0);
            }
            if (!Avis[m - 1][j]) {
                Avis[m - 1][j] = true;
                dfs(heights, m - 1, j, 1);
            }
        }
        vector<vector<int>> ret;
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++) {
                if (Pvis[i][j] && Avis[i][j])
                {
                    vector<int> v({ i, j });
                    ret.push_back(v);
                }
            }
        return ret;
    }

    void dfs(vector<vector<int>>& heights, int i, int j, int flag) {
        for (int k = 0; k < 4; k++) {
            int x = i + dx[k], y = j + dy[k];
            if (flag == 0) {
                if (x >= 0 && y >= 0 && x < m && y < n && !Pvis[x][y] && heights[x][y] >= heights[i][j]) {
                    Pvis[x][y] = true;
                    dfs(heights, x, y, 0);
                }
            }
            else {
                if (x >= 0 && y >= 0 && x < m && y < n && !Avis[x][y] && heights[x][y] >= heights[i][j]) {
                    Avis[x][y] = true;
                    dfs(heights, x, y, 1);
                }
            }
        }
    }
};